/*
 * memory.c - Mokri
 * Contributors: xMine
 * (Any new Contributor may add himself/herself to the list)
 * Fixes to be made: 
 * Source: http://www.smksoftware.com/products/liballoc/
 */

#include "memory.h"

extern const void kernel_start; // Variablen vom Linker
extern const void kernel_end;

extern const void data_end;

extern const void _sbss;
extern const void _ebss;

uint32_t userspace; // Ab dort beginnt der Userspace
uint32_t min_page;  // userspace / 4096

uint32_t MapSize;

// Wenn Bit gesetzt ist, ist die Speicherstelle belegt!
static uint32_t memorymap [MEMORY_MAP_SIZE];

/* Kopiert einen Speicherbereich
 * Parameter: Zielort, Quelle, Länge
 * Rückgaben: Zielbuffer
 */
void *memcpy (void *dst, const void *src, int len) {
    if (len < 1) return dst;
    int i;
    void *_dst = dst;
    void *_src = (void*)src;
    for (i=0; i<len; i++) {
        *((char*)_dst) = *((char*)_src);
        _dst++;
        _src++;
    }

    return dst;
}

/* Füllt einen Speicherbereich
 * Parameter: Zielort, Füllzeichen, Länge
 * Rückgaben: Zielort
 */
void *memset (void *dst, char c, int len) {
    if (len < 1) return dst;
    int i;
    char *_dst = (char*)dst;
    for (i=0;i<len;i++) {
	*_dst = c;
        _dst++;
    }

    return dst;
}

/* Gibt die aktuelle RAM Auslastung in Bytes zurück
 * Parameter: Keine
 * Rückgaben: Alloziierte Bytes insgesamt
 */
size_t get_used_memory () {
	return 0; //benutzter_ram;
}

/* Markiert eine Page als frei
 * Parameter: Adresse der Page
 * Rückgaben: Keine
 */
void pmm_free (void *page) {
	size_t index = (size_t) page / 4096 / 32;
	memorymap[index] &= ~(1 << (((size_t) page / 4096) & (32 - 1)));
}

/* Findet eine freie Page, markiert diese als benutzt und gibt ihre Adresse zurück
 * Parameter: Keine
 * Rückgaben: Adresse
 */
void *pmm_alloc () {
	// 1. Freie Page suchen
	uint32_t i, j;
	// Durchsucht den Bereich nach den ersten 16MB im RAM, damit dieser Bereich für DMA frei bleibt
	i = (min_page/32) + 1;
	
	for (; i<MapSize; i++) {
		if (memorymap[i] != 0xFFFFFFFF) { // Wenn die Pages wieso voll sind, braucht man sie nicht zu durchsuchen
			for (j=0; j<32; j++) {
				if ( !(memorymap[i] & (1 << j)) ) { // Page frei?
					pmm_mark_page_as_used ((void*)(i*128*1024+j*4096));
					if (i < (min_page/32) + 1) {
						kernel_panic ("pmm_alloc: Page unterhalb Userspace");
					}
					
					return (void*)(i*128*1024+j*4096); // Page adresse berechnen und zurück geben
				}
			}
		}
	}

	kernel_panic ("pmm_alloc: Out of Memory!");
	return NULL; // Oh mein Gott, der RAM ist voll Oo
}

/* Zeigt an, ob eine Page frei ist oder nicht
 * Parameter: Pagenummer
 * Rückgaben: TRUE = Page ist frei, sonst FALSE
 */
BOOL pmm_is_page_free (int page) {
	unsigned int map, index;
	index = page / 32;
	map = page - index * 32;
	
	if (!(memorymap[index] & (1 << map))) {
		return TRUE;
	}
	
	return FALSE;
}

/* Überprüft ob ein Bereich von hintereinander liegenden Pages frei ist
 * Parameter: Start Page, Anzahl
 * Rückgaben: TRUE wenn diese frei sind, ansonsten FALSE
 */
BOOL pmm_is_page_range_free (int page, int num) {
	int i;
	for (i=0; i < num; i++) {
		if (!pmm_is_page_free (page+i)) {
			return FALSE;
		}
	}
	
	return TRUE;
}

/* Sucht mehrere freie zusammenhängende Pages und gibt bei Erfolg die Position zurück
 * Parameter: Größe des angeforderten Speichers in Byte
 * Rückgaben: Bei Erfolg die Position des Speichers, ansonsten NULL
 */
void *pmm_range_alloc (uint32_t size) {
	uint16_t num = size/4096;
	uint16_t i, j, k;
	
	if (size % 4096 > 0) {
		num++;
	}
	
	i = (min_page/32) + 1;
	for (; i<MapSize; i++) {
		if (memorymap[i] != 0xFFFFFFFF) { // Wenn die Pages wieso voll sind, braucht man sie nicht zu durchsuchen
			for (j=0; j<32; j++) {
				if ( pmm_is_page_range_free (i*32+j, num) ) { // Page frei?
					
					for (k = j; k < j+num; k++) { // Pages als benutzt markieren
						pmm_mark_page_as_used ((void*)(i*128*1024+k*4096));
					}
					
					return (void*)(i*128*1024+j*4096); // Page adresse berechnen und zurück geben
				}
			}
		}
	}
	
	return NULL; // Oh mein Gott, der RAM ist voll Oo
}

/* Diese Funktion sucht einen zusammenhängenden Block unterhalb von 16MB im RAM für DMA Operationen
 * Parameter: Größe des Bereichs in Byte
 * Rückgaben: Zeiger auf den Bereich, ansonsten NULL
 */
void *pmm_alloc_dma (uint32_t size) {
	unsigned int num = size/4096+1;
	unsigned int i, j;
	// Durchsucht einen Bereich von 1,25 - 16 MB im RAM
	for (i=70; i<128; i++) {
		if (memorymap[i] != 0xFFFFFFFF) { // Wenn die Pages wieso voll sind, braucht man sie nicht zu durchsuchen
			for (j=0; j<32; j++) {
				if ( pmm_is_page_range_free (i*32+j, num) ) { // Page frei?
					unsigned int k;
					for (k = j; k < j+num; k++) { // Pages als benutzt markieren
						pmm_mark_page_as_used ((void*)(i*128*1024+k*4096));
					}
					
					return (void*)(i*128*1024+j*4096); // Page adresse berechnen und zurück geben
				}
			}
		}
	}
	
	return NULL; // Oh mein Gott, der RAM ist voll Oo
}

/* Markiert eine Page als belegt - nur INTERN!
 * Parameter: Adresse
 * Rückgaben: Keine
 */
void pmm_mark_page_as_used (void *page) { // Erinnert mich irgendwie an can_this_function_name_even_be_longer () :-p
	size_t index = (size_t) page / 4096 / 32;
	memorymap[index] |= (1 << (((size_t) page / 4096) & (32 - 1)));
}

/* Markiert eine Page als belegt - nur INTERN
 * Parameter: Index, Bit
 * Rückgaben: Keine
 */
void inline pmm_mark_page_as_used_ex (size_t index, size_t bit) {
	memorymap[index] |= (1 << bit); // Bit setzen -> belegt
}

/* Startet den Memory Manager
 * Parameter: Multiboot_info Structure von GRUB
 * Rückgaben: Keine
 */
void pmm_init (struct multiboot_info *mb) {
	struct mbs_mmap *mmap = (struct mbs_mmap *)mb->mbs_mmap_addr; // Memorymap
	struct mbs_mmap *mmap_end = (void*) ((uintptr_t)mb->mbs_mmap_addr + mb-> mbs_mmap_length);

	// Ab dieser Adresse beginnt der Userspace
	userspace = (uint32_t)0x1000000+(uint32_t)&kernel_start+(uint32_t)&_ebss+(uint32_t)&kernel_end;
	
	if (userspace % 4096 > 0) { // Auf eine Page ausrichten
		userspace += 4096 - (userspace % 4096);
	}
	
	min_page = userspace/4096;
	
	MapSize = (unsigned int)((mb->mbs_mem_lower+mb->mbs_mem_upper)/4/32); // RAM Größe von GRUB in KiloBytes
	//printf ("[ RamSize: %i ]", (int)mb->mbs_mem);

	uintptr_t addr;
	while (mmap < mmap_end) {
		if (mmap->Type == 1) { // Ist der Speicherbereich frei?
			addr = (uintptr_t)((unsigned int)mmap->BaseAddr);
			uintptr_t end_addr = addr + mmap->Length;

			while (addr < end_addr) {
				if (addr > (uintptr_t)&kernel_end) {
					pmm_free ((void*) addr); // Speicherbereich als frei markieren
				}
				addr += 0x1000; // == 4kb (eine Page)
			}
		}

		mmap++;
	}
	
	// Den Kernel als belegt markieren
	uint32_t p;
	for (p=0; p<min_page; p++) {
		pmm_mark_page_as_used ((void*)(p*4096));
	}

	// Videospeicher ist auch belegt...
	for (p=184; p<192; p++) {
		pmm_mark_page_as_used ((void*)(p*4096));
	}

}
/** Wrapperfunktionen für liballoc **/
lock_t alloc_lock = UNLOCKED;

int liballoc_lock() {
	alloc_lock = LOCKED;
	return 0;
}

int liballoc_unlock() {
	alloc_lock = UNLOCKED;
	return 0;
}

void* liballoc_alloc(size_t pages) {
	return pmm_range_alloc (pages*4096);
}

int liballoc_free(void* ptr, size_t pages) {
	void *ende = (void*)(ptr + pages*4096);
	while (ptr < ende) {
		pmm_free (ptr);
		ptr += 4096;
	}
	
	return 0;
}

/** Der komplette folgende Code stammt nicht vom Projekt selber, sondern ist eine Portierung
 ** eines Memory Managers. Quelle: http://www.smksoftware.com/products/liballoc/
 **/

/* BSD Lizenz
 * Copyright (c) 2009, SMK Software
 * 
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - Neither the name of SMK Software nor the
 *   names of its contributors may be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY SMK SOFTWARE ”AS IS” AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL SMK SOFTWARE BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/**  Durand's Amazing Super Duper Memory functions.  */

#define ALIGNMENT	4ul	///< This is the byte alignment that memory must be allocated on. IMPORTANT for GTK and other stuff.

#define ALIGN_TYPE	unsigned short
#define ALIGN_INFO	sizeof(ALIGN_TYPE)	///< Alignment information is stored right before the pointer. This is the number of bytes of information stored there.

#define USE_CASE1
#define USE_CASE2
#define USE_CASE3
#define USE_CASE4
#define USE_CASE5

/** This macro will conveniently align our pointer upwards */
#define ALIGN( ptr )	\
if ( ALIGNMENT > 1 )	\
{			\
uintptr_t diff;		\
ptr = (void*)((uintptr_t)ptr + ALIGN_INFO);	\
diff = (uintptr_t)ptr & (ALIGNMENT-1);	\
if ( diff != 0 )	\
{			\
diff = ALIGNMENT - diff;	\
ptr = (void*)((uintptr_t)ptr + diff);	\
}					\
*((ALIGN_TYPE*)((uintptr_t)ptr - ALIGN_INFO)) = \
diff + ALIGN_INFO;				\
}

#define UNALIGN( ptr )	\
if ( ALIGNMENT > 1 )	\
{			\
uintptr_t diff = *((ALIGN_TYPE*)((uintptr_t)ptr - ALIGN_INFO));	\
if ( diff < (ALIGNMENT + ALIGN_INFO) )	\
{					\
ptr = (void*)((uintptr_t)ptr - diff);	\
}					\
}

#define LIBALLOC_MAGIC	0xc001c0de
#define LIBALLOC_DEAD	0xdeaddead

/** A structure found at the top of all system allocated 
* memory blocks. It details the usage of the memory block.
*/
struct liballoc_major
{
	struct liballoc_major *prev;		///< Linked list information.
	struct liballoc_major *next;		///< Linked list information.
	unsigned int pages;			///< The number of pages in the block.
	unsigned int size;			///< The number of pages in the block.
	unsigned int usage;			///< The number of bytes used in the block.
	struct liballoc_minor *first;		///< A pointer to the first allocated memory in the block.	
};

/** This is a structure found at the beginning of all
* sections in a major block which were allocated by a
* malloc, calloc, realloc call.
*/
struct	liballoc_minor
{
	struct liballoc_minor *prev;		///< Linked list information.
	struct liballoc_minor *next;		///< Linked list information.
	struct liballoc_major *block;		///< The owning block. A pointer to the major structure.
	unsigned int magic;			///< A magic number to idenfity correctness.
	unsigned int size; 			///< The size of the memory allocated. Could be 1 byte or more.
	unsigned int req_size;			///< The size of memory requested.
};

static struct liballoc_major *l_memRoot = NULL;	///< The root memory block acquired from the system.
static struct liballoc_major *l_bestBet = NULL; ///< The major with the most free memory.

static int l_pageSize  = 4096;			///< The size of an individual page. Set up in liballoc_init.
static int l_pageCount = 16;			///< The number of pages to request per chunk. Set up in liballoc_init.
static long long l_allocated = 0;		///< Running total of allocated memory.
static long long l_inuse	 = 0;		///< Running total of used memory.

static long long l_warningCount = 0;		///< Number of warnings encountered
static long long l_errorCount = 0;		///< Number of actual errors
static long long l_possibleOverruns = 0;	///< Number of possible overruns

// ***********   HELPER FUNCTIONS  *******************************

static void* 	liballoc_memset(void* s, int c, size_t n)
{
	int i;
	for ( i = 0; i < n ; i++)
		((char*)s)[i] = c;
	
	return s;
}

static void* 	liballoc_memcpy(void* s1, const void* s2, size_t n)
{
	char *cdest;
	char *csrc;
	unsigned int *ldest = (unsigned int*)s1;
	unsigned int *lsrc  = (unsigned int*)s2;
	
	while ( n >= sizeof(unsigned int) )
	{
		*ldest++ = *lsrc++;
		n -= sizeof(unsigned int);
	}
	
	cdest = (char*)ldest;
	csrc  = (char*)lsrc;
	
	while ( n > 0 )
	{
		*cdest++ = *csrc++;
		n -= 1;
	}
	
	return s1;
}

#if defined DEBUG || defined INFO
static void liballoc_dump()
{
	#ifdef DEBUG
	struct liballoc_major *maj = l_memRoot;
	struct liballoc_minor *min = NULL;
	#endif
	
	printf( "liballoc: ------ Memory data ---------------\n");
	printf( "liballoc: System memory allocated: %i bytes\n", l_allocated );
	printf( "liballoc: Memory in used (malloc'ed): %i bytes\n", l_inuse );
	printf( "liballoc: Warning count: %i\n", l_warningCount );
	printf( "liballoc: Error count: %i\n", l_errorCount );
	printf( "liballoc: Possible overruns: %i\n", l_possibleOverruns );
	
	#ifdef DEBUG
	while ( maj != NULL )
	{
		printf( "liballoc: %x: total = %i, used = %i\n",
			maj, 
			maj->size,
			maj->usage );
			
			min = maj->first;
			while ( min != NULL )
			{
				printf( "liballoc:    %x: %i bytes\n",
					min, 
					min->size );
					min = min->next;
			}
			
			maj = maj->next;
	}
	#endif
	
}
#endif

// ***************************************************************

static struct liballoc_major *allocate_new_page( unsigned int size )
{
	unsigned int st;
	struct liballoc_major *maj;
	
	// This is how much space is required.
	st  = size + sizeof(struct liballoc_major);
	st += sizeof(struct liballoc_minor);
	
	// Perfect amount of space?
	if ( (st % l_pageSize) == 0 )
		st  = st / (l_pageSize);
	else
		st  = st / (l_pageSize) + 1;
	// No, add the buffer. 
	
	
	// Make sure it's >= the minimum size.
	if ( st < l_pageCount ) st = l_pageCount;
	
	maj = (struct liballoc_major*)liballoc_alloc( st );
	
	if ( maj == NULL ) 
	{
		l_warningCount += 1;
		#if defined DEBUG || defined INFO
		printf( "liballoc: WARNING: liballoc_alloc( %i ) return NULL\n", st );
		#endif
		return NULL;	// uh oh, we ran out of memory.
	}
	
	maj->prev 	= NULL;
	maj->next 	= NULL;
	maj->pages 	= st;
	maj->size 	= st * l_pageSize;
	maj->usage 	= sizeof(struct liballoc_major);
	maj->first 	= NULL;
	
	l_allocated += maj->size;
	
	#ifdef DEBUG
	printf( "liballoc: Resource allocated %x of %i pages (%i bytes) for %i size.\n", maj, st, maj->size, size );
	
	printf( "liballoc: Total memory usage = %i KB\n",  (int)((l_allocated / (1024))) );
	#endif
	
	return maj;
}

void *malloc(size_t req_size)
{
	int startedBet = 0;
	unsigned long long bestSize = 0;
	void *p = NULL;
	uintptr_t diff;
	struct liballoc_major *maj;
	struct liballoc_minor *min;
	struct liballoc_minor *new_min;
	size_t size = req_size;
	
	// For alignment, we adjust size so there's enough space to align.
	if ( ALIGNMENT > 1 )
	{
		size += ALIGNMENT + ALIGN_INFO;
	}
	// So, ideally, we really want an alignment of 0 or 1 in order
	// to save space.
	
	liballoc_lock();
	
	if ( size == 0 )
	{
		l_warningCount += 1;
		#if defined DEBUG || defined INFO
		printf( "liballoc: WARNING: alloc( 0 ) called from %x\n",
			__builtin_return_address(0) );
			#endif
			liballoc_unlock();
			return malloc(1);
	}
	
	
	if ( l_memRoot == NULL )
	{
		#if defined DEBUG || defined INFO
		#ifdef DEBUG
		printf( "liballoc: initialization of liballoc " VERSION "\n" );
		#endif
		atexit( liballoc_dump );
		#endif
		
		// This is the first time we are being used.
		l_memRoot = allocate_new_page( size );
		if ( l_memRoot == NULL )
		{
			liballoc_unlock();
			#ifdef DEBUG
			printf( "liballoc: initial l_memRoot initialization failed\n", p); 
			#endif
			return NULL;
		}
		
		#ifdef DEBUG
		printf( "liballoc: set up first memory major %x\n", l_memRoot );
		#endif
	}
	
	#ifdef DEBUG
	printf( "liballoc: %x malloc( %i ): ", 
		__builtin_return_address(0),
		size );
		#endif
		
		// Now we need to bounce through every major and find enough space....
		
		maj = l_memRoot;
		startedBet = 0;
		
		// Start at the best bet....
		if ( l_bestBet != NULL )
		{
			bestSize = l_bestBet->size - l_bestBet->usage;
			
			if ( bestSize > (size + sizeof(struct liballoc_minor)))
			{
				maj = l_bestBet;
				startedBet = 1;
			}
		}
		
		while ( maj != NULL )
		{
			diff  = maj->size - maj->usage;	
			// free memory in the block
			
			if ( bestSize < diff )
			{
				// Hmm.. this one has more memory then our bestBet. Remember!
				l_bestBet = maj;
				bestSize = diff;
			}
			
			
			#ifdef USE_CASE1
			
			// CASE 1:  There is not enough space in this major block.
			if ( diff < (size + sizeof( struct liballoc_minor )) )
			{
				#ifdef DEBUG
				printf( "CASE 1: Insufficient space in block %x\n", maj);
				#endif
				
				// Another major block next to this one?
				if ( maj->next != NULL ) 
				{
					maj = maj->next;		// Hop to that one.
					continue;
				}
				
				if ( startedBet == 1 )		// If we started at the best bet,
				{							// let's start all over again.
				maj = l_memRoot;
				startedBet = 0;
				continue;
				}
				
				// Create a new major block next to this one and...
				maj->next = allocate_new_page( size );	// next one will be okay.
				if ( maj->next == NULL ) break;			// no more memory.
					maj->next->prev = maj;
				maj = maj->next;
				
				// .. fall through to CASE 2 ..
			}
			
			#endif
			
			#ifdef USE_CASE2
			
			// CASE 2: It's a brand new block.
			if ( maj->first == NULL )
			{
				maj->first = (struct liballoc_minor*)((uintptr_t)maj + sizeof(struct liballoc_major) );
				
				
				maj->first->magic 		= LIBALLOC_MAGIC;
				maj->first->prev 		= NULL;
				maj->first->next 		= NULL;
				maj->first->block 		= maj;
				maj->first->size 		= size;
				maj->first->req_size 	= req_size;
				maj->usage 	+= size + sizeof( struct liballoc_minor );
				
				
				l_inuse += size;
				
				
				p = (void*)((uintptr_t)(maj->first) + sizeof( struct liballoc_minor ));
				
				ALIGN( p );
				
				#ifdef DEBUG
				printf( "CASE 2: returning %x\n", p);
				#endif
				liballoc_unlock();		// release the lock
				return p;
			}
			
			#endif
			
			#ifdef USE_CASE3
			
			// CASE 3: Block in use and enough space at the start of the block.
			diff =  (uintptr_t)(maj->first);
			diff -= (uintptr_t)maj;
			diff -= sizeof(struct liballoc_major);
			
			if ( diff >= (size + sizeof(struct liballoc_minor)) )
			{
				// Yes, space in front. Squeeze in.
				maj->first->prev = (struct liballoc_minor*)((uintptr_t)maj + sizeof(struct liballoc_major) );
				maj->first->prev->next = maj->first;
				maj->first = maj->first->prev;
				
				maj->first->magic 	= LIBALLOC_MAGIC;
				maj->first->prev 	= NULL;
				maj->first->block 	= maj;
				maj->first->size 	= size;
				maj->first->req_size 	= req_size;
				maj->usage 			+= size + sizeof( struct liballoc_minor );
				
				l_inuse += size;
				
				p = (void*)((uintptr_t)(maj->first) + sizeof( struct liballoc_minor ));
				ALIGN( p );
				
				#ifdef DEBUG
				printf( "CASE 3: returning %x\n", p); 
				#endif
				liballoc_unlock();		// release the lock
				return p;
			}
			
			#endif
			
			
			#ifdef USE_CASE4
			
			// CASE 4: There is enough space in this block. But is it contiguous?
			min = maj->first;
			
			// Looping within the block now...
			while ( min != NULL )
			{
				// CASE 4.1: End of minors in a block. Space from last and end?
				if ( min->next == NULL )
				{
					// the rest of this block is free...  is it big enough?
					diff = (uintptr_t)(maj) + maj->size;
					diff -= (uintptr_t)min;
					diff -= sizeof( struct liballoc_minor );
					diff -= min->size; 
					// minus already existing usage..
					
					if ( diff >= (size + sizeof( struct liballoc_minor )) )
					{
						// yay....
						min->next = (struct liballoc_minor*)((uintptr_t)min + sizeof( struct liballoc_minor ) + min->size);
						min->next->prev = min;
						min = min->next;
						min->next = NULL;
						min->magic = LIBALLOC_MAGIC;
						min->block = maj;
						min->size = size;
						min->req_size = req_size;
						maj->usage += size + sizeof( struct liballoc_minor );
						
						l_inuse += size;
						
						p = (void*)((uintptr_t)min + sizeof( struct liballoc_minor ));
						ALIGN( p );
						
						#ifdef DEBUG
						printf( "CASE 4.1: returning %x\n", p); 
						#endif
						liballoc_unlock();		// release the lock
						return p;
					}
				}
				
				
				
				// CASE 4.2: Is there space between two minors?
				if ( min->next != NULL )
				{
					// is the difference between here and next big enough?
					diff  = (uintptr_t)(min->next);
					diff -= (uintptr_t)min;
					diff -= sizeof( struct liballoc_minor );
					diff -= min->size;
					// minus our existing usage.
					
					if ( diff >= (size + sizeof( struct liballoc_minor )) )
					{
						// yay......
						new_min = (struct liballoc_minor*)((uintptr_t)min + sizeof( struct liballoc_minor ) + min->size);
						
						new_min->magic = LIBALLOC_MAGIC;
						new_min->next = min->next;
						new_min->prev = min;
						new_min->size = size;
						new_min->req_size = req_size;
						new_min->block = maj;
						min->next->prev = new_min;
						min->next = new_min;
						maj->usage += size + sizeof( struct liballoc_minor );
						
						l_inuse += size;
						
						p = (void*)((uintptr_t)new_min + sizeof( struct liballoc_minor ));
						ALIGN( p );
						
						
						#ifdef DEBUG
						printf( "CASE 4.2: returning %x\n", p); 
						#endif
						
						liballoc_unlock();		// release the lock
						return p;
					}
				}	// min->next != NULL
				
				min = min->next;
			} // while min != NULL ...
			
			
			#endif
			
			#ifdef USE_CASE5
			
			// CASE 5: Block full! Ensure next block and loop.
			if ( maj->next == NULL ) 
			{
				#ifdef DEBUG
				printf( "CASE 5: block full\n");
				#endif
				
				if ( startedBet == 1 )
				{
					maj = l_memRoot;
					startedBet = 0;
					continue;
				}
				
				// we've run out. we need more...
				maj->next = allocate_new_page( size );		// next one guaranteed to be okay
				if ( maj->next == NULL ) break;			//  uh oh,  no more memory.....
					maj->next->prev = maj;
				
			}
			
			#endif
			
			maj = maj->next;
		} // while (maj != NULL)
		
		
		
		liballoc_unlock();		// release the lock
		
		#ifdef DEBUG
		printf( "All cases exhausted. No memory available.\n");
		#endif
		#if defined DEBUG || defined INFO
		printf( "liballoc: WARNING: malloc( %i ) returning NULL.\n", size);
		liballoc_dump();
		#endif
		return NULL;
}

void free(void *ptr)
{
	struct liballoc_minor *min;
	struct liballoc_major *maj;
	
	if ( ptr == NULL ) 
	{
		l_warningCount += 1;
		#if defined DEBUG || defined INFO
		printf( "liballoc: WARNING: free( NULL ) called from %x\n",
			__builtin_return_address(0) );
			#endif
			return;
	}
	
	UNALIGN( ptr );
	
	liballoc_lock();		// lockit
	
	
	min = (struct liballoc_minor*)((uintptr_t)ptr - sizeof( struct liballoc_minor ));
	
	
	if ( min->magic != LIBALLOC_MAGIC ) 
	{
		l_errorCount += 1;
		
		// Check for overrun errors. For all bytes of LIBALLOC_MAGIC 
		if ( 
			((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) || 
			((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) || 
			((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF)) 
			)
		{
			l_possibleOverruns += 1;
			#if defined DEBUG || defined INFO
			printf( "liballoc: ERROR: Possible 1-3 byte overrun for magic %x != %x\n",
				min->magic,
				LIBALLOC_MAGIC );
				#endif
		}
		
		
		if ( min->magic == LIBALLOC_DEAD )
		{
			#if defined DEBUG || defined INFO
			printf( "liballoc: ERROR: multiple free() attempt on %x from %x.\n", 
				ptr,
				__builtin_return_address(0) );
				#endif
		}
		else
		{
			#if defined DEBUG || defined INFO
			printf( "liballoc: ERROR: Bad free( %x ) called from %x\n",
				ptr,
				__builtin_return_address(0) );
				#endif
		}
		
		// being lied to...
		liballoc_unlock();		// release the lock
		return;
	}
	
	#ifdef DEBUG
	printf( "liballoc: %x free( %x ): ", 
		__builtin_return_address( 0 ),
		ptr );
		#endif
		
		
		maj = min->block;
		
		l_inuse -= min->size;
		
		maj->usage -= (min->size + sizeof( struct liballoc_minor ));
		min->magic  = LIBALLOC_DEAD;		// No mojo.
		
		if ( min->next != NULL ) min->next->prev = min->prev;
		if ( min->prev != NULL ) min->prev->next = min->next;
		
		if ( min->prev == NULL ) maj->first = min->next;	
		// Might empty the block. This was the first
		// minor.
		
		
		// We need to clean up after the majors now....
		
		if ( maj->first == NULL )	// Block completely unused.
		{
			if ( l_memRoot == maj ) l_memRoot = maj->next;
			if ( l_bestBet == maj ) l_bestBet = NULL;
			if ( maj->prev != NULL ) maj->prev->next = maj->next;
			if ( maj->next != NULL ) maj->next->prev = maj->prev;
			l_allocated -= maj->size;
			
			liballoc_free( maj, maj->pages );
		}
		else
		{
			if ( l_bestBet != NULL )
			{
				int bestSize = l_bestBet->size  - l_bestBet->usage;
				int majSize = maj->size - maj->usage;
				
				if ( majSize > bestSize ) l_bestBet = maj;
			}
			
		}
		
		
		#ifdef DEBUG
		printf( "OK\n");

		#endif
		
		liballoc_unlock();		// release the lock
}

void* calloc(size_t nobj, size_t size)
{
	int real_size;
	void *p;
	
	real_size = nobj * size;
	
	p = malloc( real_size );
	
	liballoc_memset( p, 0, real_size );
	
	return p;
}



void* realloc(void *p, size_t size)
{
	void *ptr;
	struct liballoc_minor *min;
	int real_size;
	
	// Honour the case of size == 0 => free old and return NULL
	if ( size == 0 )
	{
		free( p );
		return NULL;
	}
	
	// In the case of a NULL pointer, return a simple malloc.
	if ( p == NULL ) return malloc( size );
	
	// Unalign the pointer if required.
	ptr = p;
	UNALIGN(ptr);
	
	liballoc_lock();		// lockit
	
	min = (struct liballoc_minor*)((uintptr_t)ptr - sizeof( struct liballoc_minor ));
	
	// Ensure it is a valid structure.
	if ( min->magic != LIBALLOC_MAGIC ) 
	{
		l_errorCount += 1;
		
		// Check for overrun errors. For all bytes of LIBALLOC_MAGIC 
		if ( 
			((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) || 
			((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) || 
			((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF)) 
			)
		{
			l_possibleOverruns += 1;
			#if defined DEBUG || defined INFO
			printf( "liballoc: ERROR: Possible 1-3 byte overrun for magic %x != %x\n",
				min->magic,
				LIBALLOC_MAGIC );
				#endif
		}
		
		
		if ( min->magic == LIBALLOC_DEAD )
		{
			#if defined DEBUG || defined INFO
			printf( "liballoc: ERROR: multiple free() attempt on %x from %x.\n", 
				ptr,
				__builtin_return_address(0) );
				#endif
		}
		else
		{
			#if defined DEBUG || defined INFO
			printf( "liballoc: ERROR: Bad free( %x ) called from %x\n",
				ptr,
				__builtin_return_address(0) );
				#endif
		}
		
		// being lied to...
		liballoc_unlock();		// release the lock
		return NULL;
	}	
	
	// Definitely a memory block.
	
	real_size = min->req_size;
	
	if ( real_size >= size ) 
	{
		min->req_size = size;
		liballoc_unlock();
		return p;
	}
	
	liballoc_unlock();
	
	// If we got here then we're reallocating to a block bigger than us.
	ptr = malloc( size );	// We need to allocate new memory
	liballoc_memcpy( ptr, p, real_size );
	free (p);
	
	return ptr;
}
